package arithmetic;

import utils.PrintUtil;

import java.util.*;

/**
 * @Author: Jie
 * @Date: 2019/1/17 14:27
 * @Function :1. 两数之和，每个元素只能用一遍
 * <p>
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 *
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 *
 * 示例:
 *
 * 给定 nums = [2, 7, 11, 15], target = 9
 *
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class A_08_TwoSum {
    public static void main(String[] args) {
        //方法1 暴力法， 2个for 循环
        //方法2 2遍map, 第一次存储每个数与下标，第二次查找Map中key
        //方法3 1遍map，在一次循环中 加入map,并取出，当遇到余数时返回。
//        int[] ints = twoSum(new int[]{3, 2, 4}, 6);
        int[] ints = twoSum(new int[]{3, 3}, 6);

        PrintUtil.print(ints);
    }


    /**
     * 思路，拿到一个值，寻找另一个值。
     * 一遍 hash 表,时间On 空间On
     *
     *  如果 nums[i]==nums[i-1] continue
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {

            //用第二个值，判断第一个值的大小。
            int findFirstNum = target - nums[i];
            if (map.containsKey(findFirstNum)) {//找到 第一个值。
                Integer start = map.get(findFirstNum);
                    return new int[]{start, i};
            }
            map.put(nums[i], i);//记录，value ，index
        }
        return new int[0];
    }


}
